package com.bo.day20241121;

import java.util.*;

/**
 * 图的深度优先遍历
 *
 * @Author: gpb
 * @Date: 2024/11/22 14:50
 * @Description:
 */
public class DFS {
    public static void dfs (Node node, Set<Node> set) {
        if (set.contains(node) || node == null) {
            return;
        }
        System.out.print(node.value + " ");
        set.add(node);
        for (Node nest : node.nexts) {
            dfs(nest, set);
        }
    }

    // 从node出发，进行宽度优先遍历
    public static void bfs1 (Node start) {
        if (start == null) {
            return;
        }
        // 宽度优先遍历队列
        Stack<Node> stack = new Stack<>();
        Set<Node> set = new HashSet<>();
        stack.push(start);
        set.add(start);
        System.out.print(start.value + " ");
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            for (Node next : pop.nexts) {
                if (!set.contains(next)) {
                    // 首先把自己压入栈中
                    stack.push(next);
                    // 然后再把next压入栈中
                    set.add(next);
                    System.out.print(next.value + " ");
                }
            }
        }
    }
}
